#ifndef __MY_QUEUE_H__
#define __MY_QUEUE_H__

#include <iostream>
#include "global.h"

using namespace std;

template <class Type>
class MyQueue {
public:
	MyQueue();
	~MyQueue();

	bool push(Type val);
	bool pop();

	Type front();
	Type back();

	bool empty();
	size_t size();

private:
	NODE<Type> *head;
	NODE<Type> *tail;

	size_t node_num;
};

template <class Type>
MyQueue<Type>::MyQueue() {
	head = NULL;
	tail = NULL;
	node_num = 0;
}

template <class Type>
MyQueue<Type>::~MyQueue() {
	NODE<Type> *node, *tmp_node;
	node = head;
	while (node) {
		tmp_node = node;
		node = node->next;
		free(tmp_node);
	}

	head = NULL;
	tail = NULL;
	node_num = 0;
}

template <class Type>
Type MyQueue<Type>::front() {
	if (head == NULL) {
		cout << "Error, empty queue!" << endl;
		return (Type) 0;
	}

	return head->val;
}

template <class Type>
Type MyQueue<Type>::back() {
	if (tail == NULL) {
		cout << "Error, empty queue!" << endl;
		return (Type) 0;
	}
	
	return tail->val;
}

template <class Type>
bool MyQueue<Type>::push(Type val) {
	NODE<Type> *node = (NODE<Type> *)malloc(sizeof(NODE<Type>));
	if (node == NULL) {
		cout << "Allocate node buffer error!" << endl;
		return false;
	}
	memset(node, 0, sizeof(NODE<Type>));

	node->val = val;

	// empty queue
	if (tail == NULL) {
		head = tail = node;
	}
	else {
		tail->next = node;
		tail = node;
	}
	++node_num;

	return true;
}

template <class Type>
bool MyQueue<Type>::pop() {
	if (head == NULL) {
		cout << "Error, empty queue!" << endl;
		return false;
	}

	// Only one node is in the queue
	if (head == tail) {
		free(head);
		head = tail = NULL;
	}
	else {
		NODE<Type> *node = head;
		head = head->next;
		free(node);
	}
	--node_num;

	return true;
}

template <class Type>
bool MyQueue<Type>::empty() {
	if (head == NULL) {
		return true;
	}
	else {
		return false;
	}
}

template <class Type>
size_t MyQueue<Type>::size() {
	return node_num;
}

#endif

